#include <stdio.h>
#include <stdlib.h>

//***线性表 顺序存储 ->单链表的定义

typedef struct LNode // 单链表节点类型
{
    int data;
    struct LNode *next;
} LNode, *LinkList; // LNode更强调节点（链表里的某个节点）、*LinkList更强调链表（即指向链表第一个节点的指针）

// 带头结点的单链表

bool InitList_head(LinkList &L)
{
    L = (LNode *)malloc(sizeof(LNode)); // 分配一个头节点
    if (L == NULL)
    {
        return false; // 内存不足，分配失败
    }
    L->next = NULL; // 头结点之后还没节点
    return true;
}

bool Empty_head(LinkList L)
{
    if (L->next == NULL) // 只有一个头结点的 “带头结点的单链表” => 空表
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool ListInsert(LinkList &L, int i, int e) // 按位序插入
{
    if (i < 1)
    {
        return false;
    }
    LNode *p;  // 指针p指向当前扫描到的节点
    int j = 0; // 当前p指向的是第几个节点
    p = L;
    while (p != NULL && j < i - 1) // 遍历链表找到第i-1个节点
    {
        p = p->next;
        j++;
    }
    if (p == NULL) // i值不合法 插到无前驱也无后继的位置
    {
        return false;
    }

    LNode *s = (LNode *)malloc(sizeof(LNode)); // 申请一个新的节点空间
    s->data = e;
    s->next = p->next; // s 指向第i个元素
    
    p->next = s; // 第i-1个元素指向 s

    return true;
}

bool InsertNextNode(LNode *p, int e) // 在指定节点p后插入元素 e
{
    if(p == NULL)
    {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s == NULL) // 内存分配失败
    {
        return false;
    }
    s->data = e;
    s->next = p->next; // s 指向 p的下一个节点
    p->next = s; // p 指向 s

    return true;
}

bool InsertPrioNode(LNode *p, int e) // 在指定节p点前插入元素 e  // 思路：先插到p之后，再交换p存的值p->data与新节点存的值e
{
    if( p==NULL )
    {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof( LNode ));
    if( s==NULL )
    {
        return false;
    }
    s->next = p->next;  // s 插入到 p 后面
    p->next = s;
    s->data = p->data;  // p s 互换data
    p->data = e;

    return true;
    
}

bool ListDelete(LinkList &L, int i, int &e)  // 按位序删除
{
    if( i<1 )
    {
        return false;
    }
    LNode *p;  // 指向当前扫描到的节点
    int j = 0;  // 当前节点位序

    p = L;
    while( p!=NULL && j<i-1 )  // 循环到 j = i-1;
    {
        p = p->next;
        j++;
    }
    if( p==NULL )  // 位置 i 不合法
    {
        return false;
    }
    if( p->next == NULL )  // 不存在第 i 位元素
    {
        return false;
    }
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;

    free(q);
    return true;

}

bool DeleteNode(LNode *p)  // 删除指定节点  // 思路：*p 与其后继 q 互换值， 删掉后继节点 q, 但
{
    if( p==NULL )
    {
        return false;
    }
    LNode *q = p->next;  // q 指向 *p 的后继节点  
    
    p->data = p->next->data;
    p->next = q->next;  // 将 q 节点从链中断开
    free(q);

    return true;

}

LNode * GetElem(LinkList &L, int i) // 按位查找 返回第i位元素
{
    if (i < 1)
    {
        return NULL;
    }
    LNode *p;  // 指针p指向当前扫描到的节点
    int j=0;   // 当前p指向的是第几个节点
    p = L;
    while (p != NULL && j < i) // 遍历链表找到第 i 个节点
    {
        p = p->next;
        j++;
    }
    // if (p == NULL) // i值不合法 -> p退出时正好时 NULL
    // {
    //     return NULL;
    // }

    return p;
}

LNode * LocateElem( LinkList L, int e )  // 按值查找
{
    LNode *p = L->next;  // 从第 1 个元素开始查找
    while( p != NULL && p->data != e)  // 循环到值为e的节点 p
    {
        p = p->next;
    }
    
    return p;
}

int Length(LinkList L)
{
    int len = 0;  // 统计表长
    LNode *p = L;
    while( p->next != NULL )
    {
        p = p->next;
        len++;
    }

    return len;
}

void PrintLink( LinkList L )
{
    printf("Length: %i \n", Length(L));

    LNode *p;
    int t=0; // 记录位序
    p = L->next;  // 从头结点之后开始打印

    printf("HeadNode ->");
    while( p != NULL )
    {
        t++;
        printf(" %i -> ", p->data);
        p = p->next;
    }
    puts(" NULL\n");
}


//尾插法建立单链表  //思路：相当于对尾结点进行尾插操作 不过要记录一下尾结点方便下一次尾插

LinkList List_TailInsert(LinkList &L)  // 正向建立单链表
{
    int x;
    L = (LinkList)malloc(sizeof(LNode));  // 建立头结点
    LNode *s, *r = L;  // r 为表尾指针
    puts("please InPut x:");
    scanf("%d", &x);

    while(x != 666)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;  // r 指向新的表尾结点
        puts("please InPut x:");
        scanf("%d", &x);

    }
    r->next = NULL;  // 尾结点指针置空
    return L;  // 返回头指针 <==> 链表


}

// 头插法建立单链表  //思路：相当于对头结点进行尾插操作 // 用于链表逆置
LinkList List_HaedInsert(LinkList &L)
{
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));  // 创建头结点
    L->next = NULL;
    puts("please InPut x:");
    scanf("%d", &x);

    while( x!=666 )  // 输入 x:666 代表结束插入
    {
        s = (LNode *)malloc(sizeof(LNode)); // 创建新节点
        s->data = x;
        s->next = L->next;
        L->next = s;
        puts("please InPut x:");
        scanf("%d", &x);
    }

    return L;
}






// int main()
// {
//     // 创建单链表
//     LinkList L;
//     InitList_head(L);
//     PrintLink(L);


//     // 按位序插入
//     for(int i=0; i<5; i++)
//     {
//         ListInsert(L, i+1, i+1); 
//     }
//     PrintLink(L);
//     // 在某节点后插入
//     LNode *np;
//     np = L->next;
//     InsertNextNode(np, 100);
//     printf("insert next node successful... node->data: %i\n", np->next->data);
//     PrintLink(L);
//     // 在某节点前插入
//     LNode *pp;
//     pp = L->next;
//     InsertPrioNode(pp, 100);
//     printf("insert prio node successful... node->data: %i\n", pp->next->data);
//     PrintLink(L);


//     // 按位序删除
//     int e;
//     ListDelete(L, 3, e);
//     printf("del NO.3 %i successful...\n", e);
//     PrintLink(L);
//     // 删指定节点
//     LNode *dp;
//     dp = L->next;
//     DeleteNode(dp);
//     printf("del node  successful... NOW node->data=%i \n", dp->data);
//     PrintLink(L);



//     // 按位序查找
//     LNode *p;
//     p = GetElem(L, 3);
//     printf("GetElem NO.3 : %i\n", p->data);

//     // 按值查找
//     LNode *q;
//     q = LocateElem(L, 4);
//     printf("LocateElem 4 :  q->data = %i\n", q->data);


//     LinkList H;

//     // 头插法建立单链表
//     List_HaedInsert(H);
//     puts("after head insert...");
//     PrintLink(H);

//     // 尾插法建立单链表
//     List_TailInsert(H);
//     puts("after tail insert...");
//     PrintLink(H);


//     return 0;


    
// }





